Iterative Solvers

4. Iterative Solvers#

So far we have used direct solvers to solve the linear system of equations. Although a direct solver can profit from the sparse matrix, it’s arithmetic complexity is sub-optimal (i.e. not linear in the number of degrees of freedom). For large-scale problems iterative solvers are a must.

The conjugate gradient (cg) method is the standard method for symmetric and positive definite matrices. It’s convergence rate depends on a preconditioner, what is a cheap approximative inverse to the matrix.

from ngsolve import *
from ngsolve.webgui import Draw

We generate a 3D geometry and mesh using the OCC constructive solid geometry (CSG) modeler:

from netgen.occ import *
cube = Box((0,0,0),(1,1,1))
cyl = Cylinder((0,0.5,0.5),X, r=0.2, h=1)
cube.faces.name = "outer"
cyl.faces.name = "cyl"
shape = cube-cyl
Draw(shape);
ngmesh = OCCGeometry(shape).GenerateMesh(maxh=0.1)
for l in range(1):
    ngmesh.Refine()
mesh = Mesh(ngmesh)
mesh.Curve(3)
Draw (mesh);
fes = H1(mesh, order=3, dirichlet="outer", wb_withedges=False)
print ("we have", fes.ndof, "unknowns")
u,v = fes.TnT()

a = BilinearForm(grad(u)*grad(v)*dx)
f = LinearForm(v*dx)

# c = Preconditioner(a, "direct", inverse="sparsecholesky")
c = Preconditioner(a, "local")
# c = Preconditioner(a, "bddc")

gfu = GridFunction(fes)
we have 189222 unknowns

assemble system and setup preconditioner in parallel:

with TaskManager():
    a.Assemble()
    f.Assemble()

solve the system using the preconditioned conjugate gradient method:

from ngsolve.krylovspace import CGSolver

with TaskManager():
    inv = CGSolver(mat=a.mat, pre=c.mat, printrates='\r', maxiter=400)
    gfu.vec.data = inv * f.vec
CG iteration 1, residual = 0.02357937034822143     
CG iteration 2, residual = 0.036539248269629385     
CG iteration 3, residual = 0.04803583710748369     
CG iteration 4, residual = 0.04826753355485345     
CG iteration 5, residual = 0.03544707042382128     
CG iteration 6, residual = 0.02924442241427406     
CG iteration 7, residual = 0.030127553489708934     
CG iteration 8, residual = 0.0277742921629846     
CG iteration 9, residual = 0.026155491369476966     
CG iteration 10, residual = 0.02541310684537252     
CG iteration 11, residual = 0.023336619745883216     
CG iteration 12, residual = 0.020687808569611787     
CG iteration 13, residual = 0.01795921210331093     
CG iteration 14, residual = 0.01608336074951512     
CG iteration 15, residual = 0.014775294419262314     
CG iteration 16, residual = 0.013169161926687397     
CG iteration 17, residual = 0.01144296179334986     
CG iteration 18, residual = 0.01015773111515155     
CG iteration 19, residual = 0.009395647366734093     
CG iteration 20, residual = 0.008739680592066592     
CG iteration 21, residual = 0.008050099064189895     
CG iteration 22, residual = 0.007220749753860234     
CG iteration 23, residual = 0.006357016392776381     
CG iteration 24, residual = 0.005534217603209726     
CG iteration 25, residual = 0.004730921676344755     
CG iteration 26, residual = 0.004017482919999034     
CG iteration 27, residual = 0.0034206728622652683     
CG iteration 28, residual = 0.002931503266812123     
CG iteration 29, residual = 0.0025062004791962175     
CG iteration 30, residual = 0.002120000795029713     
CG iteration 31, residual = 0.0017519725493129526     
CG iteration 32, residual = 0.0014304527871052233     
CG iteration 33, residual = 0.001184252104153994     
CG iteration 34, residual = 0.0009857799675508316     
CG iteration 35, residual = 0.000823571039337169     
CG iteration 36, residual = 0.0007021859729491035     
CG iteration 37, residual = 0.0006073388926455564     
CG iteration 38, residual = 0.0005305628619745718     
CG iteration 39, residual = 0.0004675763074865391     
CG iteration 40, residual = 0.00041099430949224875     
CG iteration 41, residual = 0.00035473787279223723     
CG iteration 42, residual = 0.0003058341929217276     
CG iteration 43, residual = 0.0002617637601357073     
CG iteration 44, residual = 0.0002232083281199978     
CG iteration 45, residual = 0.0001941878996336852     
CG iteration 46, residual = 0.00017280526508704977     
CG iteration 47, residual = 0.0001576108587962754     
CG iteration 48, residual = 0.00014470731158438895     
CG iteration 49, residual = 0.00013213743963028885     
CG iteration 50, residual = 0.00011973008709797844     
CG iteration 51, residual = 0.00010638995465359767     
CG iteration 52, residual = 9.210717964433535e-05     
CG iteration 53, residual = 7.789118199059881e-05     
CG iteration 54, residual = 6.594439168695368e-05     
CG iteration 55, residual = 5.588966737728374e-05     
CG iteration 56, residual = 4.86726480421635e-05     
CG iteration 57, residual = 4.318957027880525e-05     
CG iteration 58, residual = 3.892168547027423e-05     
CG iteration 59, residual = 3.5427208599247906e-05     
CG iteration 60, residual = 3.2284761864817095e-05     
CG iteration 61, residual = 2.9366433157624684e-05     
CG iteration 62, residual = 2.6249584560030033e-05     
CG iteration 63, residual = 2.304747084408644e-05     
CG iteration 64, residual = 1.974101243326374e-05     
CG iteration 65, residual = 1.6808280131115718e-05     
CG iteration 66, residual = 1.4313030640181458e-05     
CG iteration 67, residual = 1.2280099357971916e-05     
CG iteration 68, residual = 1.0770735851343987e-05     
CG iteration 69, residual = 9.661557595695976e-06     
CG iteration 70, residual = 8.936753150136419e-06     
CG iteration 71, residual = 8.405181254087689e-06     
CG iteration 72, residual = 7.890795778619652e-06     
CG iteration 73, residual = 7.325938532663062e-06     
CG iteration 74, residual = 6.617137509535326e-06     
CG iteration 75, residual = 5.821696226254289e-06     
CG iteration 76, residual = 5.0184017706341e-06     
CG iteration 77, residual = 4.214654875145235e-06     
CG iteration 78, residual = 3.5422674284170023e-06     
CG iteration 79, residual = 3.002470758271111e-06     
CG iteration 80, residual = 2.5888953812829878e-06     
CG iteration 81, residual = 2.2760784333753954e-06     
CG iteration 82, residual = 2.0449024295636423e-06     
CG iteration 83, residual = 1.8635898175939855e-06     
CG iteration 84, residual = 1.6945682214433733e-06     
CG iteration 85, residual = 1.5191984177341002e-06     
CG iteration 86, residual = 1.3361270308161315e-06     
CG iteration 87, residual = 1.1572298460496547e-06     
CG iteration 88, residual = 9.886593609178084e-07     
CG iteration 89, residual = 8.338856808736081e-07     
CG iteration 90, residual = 7.043089491424738e-07     
CG iteration 91, residual = 5.947725224375237e-07     
CG iteration 92, residual = 5.074925034231412e-07     
CG iteration 93, residual = 4.3579886214135765e-07     
CG iteration 94, residual = 3.757035997958668e-07     
CG iteration 95, residual = 3.2713550222404386e-07     
CG iteration 96, residual = 2.870658985341057e-07     
CG iteration 97, residual = 2.5129285015479785e-07     
CG iteration 98, residual = 2.208014759952778e-07     
CG iteration 99, residual = 1.9429682013537452e-07     
CG iteration 100, residual = 1.7010822676081228e-07     
CG iteration 101, residual = 1.4973918206125863e-07     
CG iteration 102, residual = 1.298400411749654e-07     
CG iteration 103, residual = 1.1179177689292227e-07     
CG iteration 104, residual = 9.651431924076041e-08     
CG iteration 105, residual = 8.288370600606733e-08     
CG iteration 106, residual = 7.126083073172443e-08     
CG iteration 107, residual = 6.120872629867229e-08     
CG iteration 108, residual = 5.313859575680102e-08     
CG iteration 109, residual = 4.6456842730521255e-08     
CG iteration 110, residual = 4.0403687975091185e-08     
CG iteration 111, residual = 3.518128484186544e-08     
CG iteration 112, residual = 3.106772565988815e-08     
CG iteration 113, residual = 2.7596843407348648e-08     
CG iteration 114, residual = 2.4615381172296945e-08     
CG iteration 115, residual = 2.2167849039059884e-08     
CG iteration 116, residual = 1.9620614830712035e-08     
CG iteration 117, residual = 1.74660961354718e-08     
CG iteration 118, residual = 1.566031162588195e-08     
CG iteration 119, residual = 1.3871090845686279e-08     
CG iteration 120, residual = 1.2100286852181736e-08     
CG iteration 121, residual = 1.0447606722573502e-08     
CG iteration 122, residual = 8.98716593493085e-09     
CG iteration 123, residual = 7.702192897832852e-09     
CG iteration 124, residual = 6.569962430098655e-09     
CG iteration 125, residual = 5.676211874262505e-09     
CG iteration 126, residual = 4.9875169915959836e-09     
CG iteration 127, residual = 4.46047412540375e-09     
CG iteration 128, residual = 4.065288939432823e-09     
CG iteration 129, residual = 3.7204650922876514e-09     
CG iteration 130, residual = 3.371066653965671e-09     
CG iteration 131, residual = 3.0496259676641122e-09     
CG iteration 132, residual = 2.7095950747432182e-09     
CG iteration 133, residual = 2.3793578438413455e-09     
CG iteration 134, residual = 2.070031404561952e-09     
CG iteration 135, residual = 1.7806020164447675e-09     
CG iteration 136, residual = 1.5336613415299791e-09     
CG iteration 137, residual = 1.3257220757643623e-09     
CG iteration 138, residual = 1.1624662168063633e-09     
CG iteration 139, residual = 1.0373626021020736e-09     
CG iteration 140, residual = 9.319758471833121e-10     
CG iteration 141, residual = 8.42668037413347e-10     
CG iteration 142, residual = 7.648114448880692e-10     
CG iteration 143, residual = 6.941195945127067e-10     
CG iteration 144, residual = 6.203584816879075e-10     
CG iteration 145, residual = 5.455939623102491e-10     
CG iteration 146, residual = 4.738483393329401e-10     
CG iteration 147, residual = 4.1091022519033886e-10     
CG iteration 148, residual = 3.570259190286109e-10     
CG iteration 149, residual = 3.1121749676827753e-10     
CG iteration 150, residual = 2.730902850917075e-10     
CG iteration 151, residual = 2.4285361981808193e-10     
CG iteration 152, residual = 2.195998829123343e-10     
CG iteration 153, residual = 1.9831895998698464e-10     
CG iteration 154, residual = 1.789047938642992e-10     
CG iteration 155, residual = 1.582001927199488e-10     
CG iteration 156, residual = 1.3836170509792588e-10     
CG iteration 157, residual = 1.1973283242206174e-10     
CG iteration 158, residual = 1.0278072176942633e-10     
CG iteration 159, residual = 8.80634430908045e-11     
CG iteration 160, residual = 7.553523721733766e-11     
CG iteration 161, residual = 6.598021336765054e-11     
CG iteration 162, residual = 5.90720470953924e-11     
CG iteration 163, residual = 5.3484445084581136e-11     
CG iteration 164, residual = 4.81952741001787e-11     
CG iteration 165, residual = 4.292451606859031e-11     
CG iteration 166, residual = 3.784297845766051e-11     
CG iteration 167, residual = 3.291112924704748e-11     
CG iteration 168, residual = 2.8339698123683537e-11     
CG iteration 169, residual = 2.40168944019767e-11     
CG iteration 170, residual = 2.009511546153381e-11     
CG iteration 171, residual = 1.6960791480675284e-11     
CG iteration 172, residual = 1.455308663793056e-11     
CG iteration 173, residual = 1.2446123000492396e-11     
CG iteration 174, residual = 1.066754713492108e-11     
CG iteration 175, residual = 9.315524978447471e-12     
CG iteration 176, residual = 8.221226531051626e-12     
CG iteration 177, residual = 7.294124437615692e-12     
CG iteration 178, residual = 6.4483526940841925e-12     
CG iteration 179, residual = 5.684352996186749e-12     
CG iteration 180, residual = 4.956117099416454e-12     
CG iteration 181, residual = 4.301079451084392e-12     
CG iteration 182, residual = 3.657085213552069e-12     
CG iteration 183, residual = 3.0441313775184163e-12     
CG iteration 184, residual = 2.521651494326158e-12     
CG iteration 185, residual = 2.0752474896860516e-12     
CG iteration 186, residual = 1.739663692021122e-12     
CG iteration 187, residual = 1.4757724978018543e-12     
CG iteration 188, residual = 1.2666290678660431e-12     
CG iteration 189, residual = 1.116969585044157e-12     
CG iteration 190, residual = 1.0000931116176701e-12     
CG iteration 191, residual = 8.971445961957425e-13     
CG iteration 192, residual = 8.004858212471564e-13     
CG iteration 193, residual = 7.054224950413475e-13     
CG iteration 194, residual = 6.084742608606343e-13     
CG iteration 195, residual = 5.164636754480694e-13     
CG iteration 196, residual = 4.3129462956419523e-13     
CG iteration 197, residual = 3.6011657545873297e-13     
CG iteration 198, residual = 3.006948547397008e-13     
CG iteration 199, residual = 2.54512288097182e-13     
CG iteration 200, residual = 2.184160842106829e-13     
CG iteration 201, residual = 1.8883017261825246e-13     
CG iteration 202, residual = 1.6314626133354632e-13     
CG iteration 203, residual = 1.421905465025107e-13     
CG iteration 204, residual = 1.2427327201656017e-13     
CG iteration 205, residual = 1.096622772416958e-13     
CG iteration 206, residual = 9.628840221891487e-14     
CG iteration 207, residual = 8.470845930603524e-14     
CG iteration 208, residual = 7.444742187738633e-14     
CG iteration 209, residual = 6.517865323870483e-14     
CG iteration 210, residual = 5.659149122693898e-14     
CG iteration 211, residual = 4.858699917175039e-14     
CG iteration 212, residual = 4.15193643913737e-14     
CG iteration 213, residual = 3.53711083172253e-14     
CG iteration 214, residual = 2.985656920543178e-14     
CG iteration 215, residual = 2.5131444109924982e-14     
CG iteration 216, residual = 2.1104238679326894e-14     
CG converged in 216 iterations to residual 2.1104238679326894e-14
Draw (gfu, draw_vol=False);